PittsburghV1, France, Analysis, bibRecord, 000711

On the Relative Strength of Split, Triangle and Quadrilateral Cuts

Identifieur interne : 000711 ( France/Analysis ); précédent : 000710; suivant : 000712

On the Relative Strength of Split, Triangle and Quadrilateral Cuts

Auteurs : Amitabh Basu [États-Unis] ; Pierre Bonami [France] ; Gérard Cornuéjols [États-Unis] ; François Margot [États-Unis]

Source :

RBID : Hal:hal-00421757

Abstract

Integer programs defined by two equations with two free integer variables and nonnegative continuous variables have three types of nontrivial facets: split, triangle or quadrilateral inequalities. In this paper, we compare the strength of these three families of inequalities. In particular we study how well each family approximates the integer hull. We show that, in a well defined sense, triangle inequalities provide a good approximation of the integer hull. The same statement holds for quadrilateral inequalities. On the other hand, the approximation produced by split inequalities may be arbitrarily bad.

Url:

https://hal.archives-ouvertes.fr/hal-00421757

DOI: 10.1007/s10107-009-0281-x

Affiliations:

France, États-Unis

Links toward previous steps (curation, corpus...)

to stream Hal, to step Corpus: 000434
to stream Hal, to step Curation: 000434
to stream Hal, to step Checkpoint: 000515
to stream Main, to step Merge: 00AD55
to stream Main, to step Curation: 00A604
to stream Main, to step Exploration: 00A604
to stream France, to step Extraction: 000711

Links to Exploration step

Hal:hal-00421757

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">On the Relative Strength of Split, Triangle and Quadrilateral Cuts</title>
<author><name sortKey="Basu, Amitabh" sort="Basu, Amitabh" uniqKey="Basu A" first="Amitabh" last="Basu">Amitabh Basu</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-87848" status="VALID">          <orgName>Tepper School of Business</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave., Pittsburgh, PA 15213, USA</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.tepper.cmu.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-67135" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-67135" type="direct"><org type="institution" xml:id="struct-67135" status="VALID">          <orgName>Carnegie Mellon University [Pittsburgh]</orgName>
          <orgName type="acronym">CMU</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave,  Pittsburgh, PA 15213</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cmu.edu/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Bonami, Pierre" sort="Bonami, Pierre" uniqKey="Bonami P" first="Pierre" last="Bonami">Pierre Bonami</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-862" status="OLD">          <idno type="RNSR">200212226K</idno>
          <orgName>Laboratoire d'informatique Fondamentale de Marseille - UMR 6166</orgName>
          <orgName type="acronym">LIF</orgName>
          <date type="start">2002</date>
          <date type="end">2011</date>
          <desc>            <address>              <addrLine>CMI 39, Rue Joliot Curie 13453 MARSEILLE CEDEX 13</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.lif.univ-mrs.fr/</ref>
          </desc>
          <listRelation>            <relation active="#struct-5033" type="direct"></relation>
            <relation active="#struct-92823" type="direct"></relation>
            <relation name="UMR6166" active="#struct-441569" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-5033" type="direct"><org type="institution" xml:id="struct-5033" status="OLD">          <idno type="IdRef">026402882</idno>
          <orgName>Université de la Méditerranée - Aix-Marseille 2</orgName>
          <date type="start">1969</date>
          <date type="end">2011</date>
          <desc>            <address>              <addrLine>58, boulevard Charles Livon - 13284 Marseille cedex 07</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univmed.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-92823" type="direct"><org type="institution" xml:id="struct-92823" status="OLD">          <idno type="IdRef">026403781</idno>
          <orgName>Université de Provence - Aix-Marseille 1</orgName>
          <date type="end">2011-12-31</date>
          <desc>            <address>              <addrLine>3, place Victor Hugo - 13331 Marseille Cedex 03</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univ-provence.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle name="UMR6166" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID">          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.cnrs.fr/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Cornuejols, Gerard" sort="Cornuejols, Gerard" uniqKey="Cornuejols G" first="Gérard" last="Cornuéjols">Gérard Cornuéjols</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-87848" status="VALID">          <orgName>Tepper School of Business</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave., Pittsburgh, PA 15213, USA</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.tepper.cmu.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-67135" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-67135" type="direct"><org type="institution" xml:id="struct-67135" status="VALID">          <orgName>Carnegie Mellon University [Pittsburgh]</orgName>
          <orgName type="acronym">CMU</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave,  Pittsburgh, PA 15213</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cmu.edu/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Margot, Francois" sort="Margot, Francois" uniqKey="Margot F" first="François" last="Margot">François Margot</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-87848" status="VALID">          <orgName>Tepper School of Business</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave., Pittsburgh, PA 15213, USA</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.tepper.cmu.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-67135" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-67135" type="direct"><org type="institution" xml:id="struct-67135" status="VALID">          <orgName>Carnegie Mellon University [Pittsburgh]</orgName>
          <orgName type="acronym">CMU</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave,  Pittsburgh, PA 15213</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cmu.edu/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00421757</idno>
<idno type="halId">hal-00421757</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-00421757</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-00421757</idno>
<idno type="doi">10.1007/s10107-009-0281-x</idno>
<date when="2009-04-23">2009-04-23</date>
<idno type="wicri:Area/Hal/Corpus">000434</idno>
<idno type="wicri:Area/Hal/Curation">000434</idno>
<idno type="wicri:Area/Hal/Checkpoint">000515</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000515</idno>
<idno type="wicri:Area/Main/Merge">00AD55</idno>
<idno type="wicri:Area/Main/Curation">00A604</idno>
<idno type="wicri:Area/Main/Exploration">00A604</idno>
<idno type="wicri:Area/France/Extraction">000711</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">On the Relative Strength of Split, Triangle and Quadrilateral Cuts</title>
<author><name sortKey="Basu, Amitabh" sort="Basu, Amitabh" uniqKey="Basu A" first="Amitabh" last="Basu">Amitabh Basu</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-87848" status="VALID">          <orgName>Tepper School of Business</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave., Pittsburgh, PA 15213, USA</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.tepper.cmu.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-67135" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-67135" type="direct"><org type="institution" xml:id="struct-67135" status="VALID">          <orgName>Carnegie Mellon University [Pittsburgh]</orgName>
          <orgName type="acronym">CMU</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave,  Pittsburgh, PA 15213</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cmu.edu/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Bonami, Pierre" sort="Bonami, Pierre" uniqKey="Bonami P" first="Pierre" last="Bonami">Pierre Bonami</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-862" status="OLD">          <idno type="RNSR">200212226K</idno>
          <orgName>Laboratoire d'informatique Fondamentale de Marseille - UMR 6166</orgName>
          <orgName type="acronym">LIF</orgName>
          <date type="start">2002</date>
          <date type="end">2011</date>
          <desc>            <address>              <addrLine>CMI 39, Rue Joliot Curie 13453 MARSEILLE CEDEX 13</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.lif.univ-mrs.fr/</ref>
          </desc>
          <listRelation>            <relation active="#struct-5033" type="direct"></relation>
            <relation active="#struct-92823" type="direct"></relation>
            <relation name="UMR6166" active="#struct-441569" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-5033" type="direct"><org type="institution" xml:id="struct-5033" status="OLD">          <idno type="IdRef">026402882</idno>
          <orgName>Université de la Méditerranée - Aix-Marseille 2</orgName>
          <date type="start">1969</date>
          <date type="end">2011</date>
          <desc>            <address>              <addrLine>58, boulevard Charles Livon - 13284 Marseille cedex 07</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univmed.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-92823" type="direct"><org type="institution" xml:id="struct-92823" status="OLD">          <idno type="IdRef">026403781</idno>
          <orgName>Université de Provence - Aix-Marseille 1</orgName>
          <date type="end">2011-12-31</date>
          <desc>            <address>              <addrLine>3, place Victor Hugo - 13331 Marseille Cedex 03</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univ-provence.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle name="UMR6166" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID">          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.cnrs.fr/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Cornuejols, Gerard" sort="Cornuejols, Gerard" uniqKey="Cornuejols G" first="Gérard" last="Cornuéjols">Gérard Cornuéjols</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-87848" status="VALID">          <orgName>Tepper School of Business</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave., Pittsburgh, PA 15213, USA</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.tepper.cmu.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-67135" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-67135" type="direct"><org type="institution" xml:id="struct-67135" status="VALID">          <orgName>Carnegie Mellon University [Pittsburgh]</orgName>
          <orgName type="acronym">CMU</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave,  Pittsburgh, PA 15213</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cmu.edu/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Margot, Francois" sort="Margot, Francois" uniqKey="Margot F" first="François" last="Margot">François Margot</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-87848" status="VALID">          <orgName>Tepper School of Business</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave., Pittsburgh, PA 15213, USA</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.tepper.cmu.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-67135" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-67135" type="direct"><org type="institution" xml:id="struct-67135" status="VALID">          <orgName>Carnegie Mellon University [Pittsburgh]</orgName>
          <orgName type="acronym">CMU</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave,  Pittsburgh, PA 15213</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cmu.edu/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
</analytic>
<idno type="DOI">10.1007/s10107-009-0281-x</idno>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Integer programs defined by two equations with two free integer variables and nonnegative continuous variables have three types of nontrivial facets: split, triangle or quadrilateral inequalities. In this paper, we compare the strength of these three families of inequalities. In particular we study how well each family approximates the integer hull. We show that, in a well defined sense, triangle inequalities provide a good approximation of the integer hull. The same statement holds for quadrilateral inequalities. On the other hand, the approximation produced by split inequalities may be arbitrarily bad.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
<li>États-Unis</li>
</country>
</list>
<tree><country name="États-Unis"><noRegion><name sortKey="Basu, Amitabh" sort="Basu, Amitabh" uniqKey="Basu A" first="Amitabh" last="Basu">Amitabh Basu</name>
</noRegion>
<name sortKey="Cornuejols, Gerard" sort="Cornuejols, Gerard" uniqKey="Cornuejols G" first="Gérard" last="Cornuéjols">Gérard Cornuéjols</name>
<name sortKey="Margot, Francois" sort="Margot, Francois" uniqKey="Margot F" first="François" last="Margot">François Margot</name>
</country>
<country name="France"><noRegion><name sortKey="Bonami, Pierre" sort="Bonami, Pierre" uniqKey="Bonami P" first="Pierre" last="Bonami">Pierre Bonami</name>
</noRegion>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Amérique/explor/PittsburghV1/Data/France/Analysis

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000711 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/France/Analysis/biblio.hfd -nk 000711 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Amérique
   |area=    PittsburghV1
   |flux=    France
   |étape=   Analysis
   |type=    RBID
   |clé=     Hal:hal-00421757
   |texte=   On the Relative Strength of Split, Triangle and Quadrilateral Cuts
}}

This area was generated with Dilib version V0.6.38.
Data generation: Fri Jun 18 17:37:45 2021. Site generation: Fri Jun 18 18:15:47 2021

	Serveur d'exploration sur Pittsburgh
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur Pittsburgh

On the Relative Strength of Split, Triangle and Quadrilateral Cuts

On the Relative Strength of Split, Triangle and Quadrilateral Cuts

Source :

Abstract

Links toward previous steps (curation, corpus...)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri